package com.yang.sort;

/**
 * 比较排序
 */
public class ComparSort {

    /**
     * 冒泡排序
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] BubbleSort(int nums[]){

        for(int i = 0;i < nums.length;i ++){
            for(int j = 0;j < nums.length - i - 1;j ++){
                if(nums[j + 1] < nums[j]){
                    int tmp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
        return nums;
    }

    /**
     * 选择排序
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] SelectionSort(int nums[]){

        for(int i = 0;i < nums.length;i ++){
            int min = i;//记录下标
            for(int j = i;j < nums.length;j ++){
                if(nums[j] < nums[min]){
                    min = j;// 找到最小的下标并记录
                }
            }
            int tmp = nums[min];
            nums[min] = nums[i];
            nums[i] = tmp;
        }
        return nums;
    }

    /**
     * 插入排序
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] InsertionSort(int nums[]){

        int current;
        for(int i = 0; i < nums.length - 1;i ++){
            current = nums[i + 1];
            int pre = i;
            while (pre >= 0 && current < nums[pre]){
                nums[pre + 1] = nums[pre];
                pre --;
            }
            nums[pre + 1] = current;
        }
        return nums;
    }

    /**
     * 希尔排序（插入排序进阶版）
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] ShellSort(int nums[]){
        int len = nums.length;
        int tmp,gap = len / 2;
        while (gap > 0) {
            for(int i = gap;i < len;i ++){
                tmp = nums[i];
                int pre = i - gap;
                while (pre >= 0 && nums[pre] > tmp){
                    nums[pre + gap] = nums[pre];
                    pre -= gap;
                }
                nums[pre + gap] = tmp;
            }
            gap /= 2;
        }
        return nums;
    }

    /**
     * 快速排序
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] QuickSort(int nums[]){

        return nums;
    }

    /**
     * 归并排序
     * @param nums 排序数组
     * @return 返回排序后的数组
     */
    public static int[] MergeSort(int nums[]){

        return nums;
    }
}
